Much of the past work on asynchronous approximate Byzantine consensus hasassumed scalar inputs at the nodes [4, 8]. Recent work has yielded approximateByzantine consensus algorithms for the case when the input at each node is ad-dimensional vector, and the nodes must reach consensus on a vector in theconvex hull of the input vectors at the fault-free nodes [9, 13]. Thed-dimensional vectors can be equivalently viewed as points in the d-dimensionalEuclidean space. Thus, the algorithms in [9, 13] require the fault-free nodesto decide on a point in the d-dimensional space. In our recent work [arXiv:/1307.1051], we proposed a generalization of theconsensus problem, namely Byzantine convex consensus (BCC), which allows thedecision to be a convex polytope in the d-dimensional space, such that thedecided polytope is within the convex hull of the input vectors at thefault-free nodes. We also presented an asynchronous approximate BCC algorithm. In this paper, we propose a new BCC algorithm with optimal fault-tolerancethat also agrees on a convex polytope that is as large as possible underadversarial conditions. Our prior work [arXiv:/1307.1051] does not guaranteethe optimality of the output polytope.
展开▼
